#include <bits/stdc++.h>
using namespace std;
//Binary Tree Node
class node{
    int data;
    node* lchild;
    node* rchild;
public:
    node(int d,node* l,node* r)
    {
        data = d;
        l = lchild;
        r = rchild;
    }
};
void InOrderWithoutRecursion1(node* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    node* p = root;
    stack<node*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->rchild;
        }
    }
}


//stack<int> str2stack(string a)
//{
//    stack<int> s1;
//    for(auto i:a)
//    {
//        s1.push(i-'0');
//    }
//    return s1;
//}
//int main()
//{
//    string a,b;
//    cin>>a>>b;
//    stack<int> s1,s2,r,temp;
//    s1 = str2stack(a);
//    s2 = str2stack(b);
//    int min_size = s1.size()<s2.size()?s1.size():s2.size();
//    try {
//        int bit_sum;
//        if(temp.size()==0)
//            bit_sum = s1.top()+s2.top();
//        else{
//            bit_sum = s1.top()+s2.top()+temp.top();
//            temp.pop();
//        }
//        s1.pop();
//        s2.pop();
//        if(bit_sum>10)
//        {
//            bit_sum %= 10;
//            temp.push(1);
//        }
//        r.push(bit_sum);
//    }
//    catch()
//    {
//        if(s1.size() == 0)
//        {
//            while(s2.size()!=0)
//            {
//                if(temp.size()!=0)
//                {
//                    r.push(s2.top()+temp.top());
//                    s2.pop();
//                    temp.pop();
//                } else
//                {
//                    r.push(s2.top());
//                    s2.pop();
//                }
//
//            }
//        } else
//        {
//            while(s1.size()!=0)
//            {
//                if(temp.size()!=0)
//                {
//                    r.push(s1.top()+temp.top());
//                    s1.pop();
//                    temp.pop();
//                } else
//                {
//                    r.push(s1.top());
//                    s1.pop();
//                }
//
//            }
//        }
//
//    }
//    while(r.size()!=0)
//    {
//        cout<<r.top();
//        r.pop();
//    }
//
//}